package training;

import java.util.*;

/**
 * @Author liangzai
 * @Description:
 */
public class J25_9_20_Training {
    //设计路由器
    class Router {

        private final Deque<int[]> deque = new LinkedList<>();
        private final TreeSet<int[]> set = new TreeSet<>((o1, o2) -> {
            if (o1[1] != o2[1]) {
                return Integer.compare(o1[1], o2[1]);
            }
            if (o1[2] != o2[2]) {
                return Integer.compare(o1[2], o2[2]);
            }
            return Integer.compare(o1[0], o2[0]);
        });

        private final Map<Integer, List<Integer>> map = new HashMap<>();
        private final int memoryLimit;
        private int size;

        public Router(int memoryLimit) {
            this.memoryLimit = memoryLimit;
        }

        public boolean addPacket(int source, int destination, int timestamp) {
            int[] packet = new int[] { source, destination, timestamp };
            if (set.contains(packet)) {
                return false;
            }

            if (size >= memoryLimit) {
                forwardPacket();
            }
            set.add(packet);
            deque.offer(packet);
            map.compute(destination, (key, list) -> {
                if (list == null) {
                    list = new ArrayList<>();
                    list.add(0);
                }
                list.add(timestamp);
                return list;
            });
            size++;
            return true;
        }

        public int[] forwardPacket() {
            if (deque.isEmpty()) {
                return new int[] {};
            }
            int[] packet = deque.poll();
            set.remove(packet);
            List<Integer> list = map.get(packet[1]);
            list.set(0, list.get(0) + 1);
            size--;
            return packet;
        }

        public int getCount(int destination, int startTime, int endTime) {
            List<Integer> list = map.get(destination);
            if (list == null || list.isEmpty()) {
                return 0;
            }
            int lower = findFirstGt(list, list.get(0) + 1, startTime - 1);
            int upper = findFirstGt(list, list.get(0) + 1, endTime);
            return upper - lower;
        }

        private int findFirstGt(List<Integer> list, int l, int target) {
            int r = list.size() - 1;
            while (l <= r) {
                int m = l + (r - l) / 2;
                int val = list.get(m);
                if (val <= target) {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }
            return l;
        }
    }

}
